# 290. 单词规律
# 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
# 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

# 时间复杂度：O(n+m)，其中 n 为 pattern 的长度，m 为 str 的长度。
# 插入和查询哈希表的均摊时间复杂度均为 O(n+m)。每一个字符至多只被遍历一次。
#
# 空间复杂度：O(n+m)，其中 n 为 pattern 的长度，m 为 str 的长度。
# 最坏情况下，我们需要存储 pattern 中的每一个字符和 str 中的每一个字符串。

def wordPattern(pattern: str, s: str) -> bool:
    s_split_list = s.split(" ")
    if len(pattern) != len(s_split_list):
        return False

    re = True

    pattern_word_dict = {}
    s_dict = {}
    index = 0
    while re and index < len(pattern):
        pattern_char = pattern[index]
        s_word = s_split_list[index]

        re_pattern = True
        re_s = True

        pattern_word = pattern_word_dict.get(pattern_char)
        word = s_dict.get(s_word)

        if pattern_word is None:
            pattern_word_dict[pattern_char] = s_word
        else:
            re_pattern = pattern_word == s_word

        if word is None:
            s_dict[s_word] = pattern_char
        else:
            re_s = word == pattern_char

        re = re_pattern and re_s
        index += 1

    return re


pattern = "abba"
s = "dog cat cat dog"
result = wordPattern(pattern, s)
print(f"result:{result}")

pattern = "abba"
s = "dog dog dog dog"
result = wordPattern(pattern, s)
print(f"result:{result}")
